import java.util.Stack;

class BinaryTree{
    public static class BTNode{
        BTNode left;
        BTNode right;
        int value;
        BTNode(int value){
            this.value = value;
        }
    }
    private BTNode root;
    public void createBinaryTree(){
        BTNode node1 = new BTNode(1);
        BTNode node13 = new BTNode(13);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        root = node1;
        node3.right=node13;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node4.right = node6;
    }


    void preOrder(BTNode root){
        if(root==null){
            return;
        }
        System.out.print(root.value+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    void inOrder(BTNode root){
        if(root==null){
            return;
        }


        inOrder(root.left);

        System.out.print(root.value+" ");


        inOrder(root.right);



    }


    void postOrder(BTNode root){
        if(root==null){
            return;
        }


        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value+" ");




    }
     public void postOrderNor(BTNode root) {

         if(root == null) return;

         Stack<BTNode> stack = new Stack<>();

         BTNode cur = root;

         BTNode prev = null;

         while (cur != null || !stack.isEmpty()) {

             while (cur != null) {

                 stack.push(cur);

                 cur = cur.left;

             }

             BTNode top = stack.peek();

             if (top.right == null ) {

                 System.out.print(top.value + " ");

                 stack.pop();

                 prev = top;

             } else {

                 cur = top.right;

             }

         }

     }


    // 获取树中节点的个数
    int size(BTNode root){
        if(root==null){
            return 0;
        }

        return size(root.left)+size(root.right)+1;

    }
    // 获取叶子节点的个数
    int getLeafNodeCount(BTNode root){

        if(root==null){
            return 0;
        } else if(root.left==null&&root.right==null){
            return 1;
        }

        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);

    }
    // 子问题思路-求叶子结点个数
// 获取第K层节点的个数
    int count=0;
    int getKLevelNodeCount(BTNode root,int k){

        if (root==null){
            return 0;
        }
        if(k==1) {
            count++;
        }


        getKLevelNodeCount(root.left,k-1);
        getKLevelNodeCount(root.right,k-1);



        return count;


    }
    // 获取二叉树的高度
    int getHeight(BTNode root){

        if(root==null){
            return 0;
        }

        int n1=getHeight(root.left)+1;
        int n2=getHeight(root.right)+1;

        return n1>n2?n1:n2;



    }
    // 检测值为value的元素是否存在
    BTNode find(BTNode root, int val){


        return null;

    }
    //层序遍历
    void levelOrder(BTNode root){

    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(BTNode root){
        return true;

    }




    public static void main(String[] args) {

        BinaryTree binaryTree=new BinaryTree();
        binaryTree.createBinaryTree();

        binaryTree.postOrderNor(binaryTree.root);
////        binaryTree.preOrder(binaryTree.root);
////        System.out.println();
////        binaryTree.inOrder(binaryTree.root);
////        System.out.println();
////        binaryTree.postOrder(binaryTree.root);
////        System.out.println();
//
//        System.out.println(binaryTree.size(binaryTree.root));
//        System.out.println(binaryTree.getHeight(binaryTree.root));
//        System.out.println(binaryTree.getLeafNodeCount(binaryTree.root));
//        System.out.println(binaryTree.getKLevelNodeCount(binaryTree.root,3));



    }


}